rtk 2014

2014.1.1 (napiši funkcijo)

Dnevnik

1. podnaloga

V računalniškem sistemu imamo zabeležene dogodke in bi jih radi v strnjeni obliki shranjevali v seznam nizov. Vsak dogodek (kot na primer prijava ali odjava uporabnika, razne napake) je predstavljen z nizom znakov (kratko besedilo/vrstica), dolžine največ $100$. Dogodki so zapisani v vhodni datoteki, po en dogodek v vsaki vrstici.

Ker se nekateri dogodki včasih zgodijo večkrat zapored (ne da bi se vmes zgodil kakšen drug dogodek), jih lahko shranimo v skrajšani obliki: ponovitve zadnjega shranjenega dogodka le štejemo. Ko se kasneje pojavi nek drugačen dogodek, shranimo le, da se je zadnji shranjen dogodek ponovil še $n$-krat. V primeru, da gre le za eno dodatno ponovitev ($n = 1$, torej skupaj s prvo izpisano pojavitvijo dve pojavitvi, glej zgled), namesto sporočila o ponovitvi shranimo kar sam ponovljeni dogodek, saj ne bi s sporočilom o ponovitvi nič prihranili.

Naloga

Napiši funkcijo strni_izpis(dat), ki bo brala dogodke iz vhodne datoteke in jih shranjevala v seznam nizov.

Vhodni podatki

Tekstovna datoteka dogodki.txt z zaporedjem dogodkov. Datoteka je kodirana v utf-8. Primer:

aaa
bbbbb
ccc
ccc
ccc
dd
dd
aaa
aaa
aaa
aaa

Izhodni podatki

Funkcija naj vrne seznam nizov, v katerem so strnjeni dogodki.

['aaaa', 'bbbbb', 'ccc', 'ponovljeno se 2-krat', 'dd', 'aaa', 'ponovljeno se 3-krat']

Uradna rešitev

def strni_izpis(dat):
    """Funkcija sprejme tekstovno datoteko z zaporednimi dogodki,
       in jih strne tako, da napiše, kolikokrat se kateri ponovi."""
    prejsnja = ""
    n = 0
    with open(dat, 'r', encoding='utf-8') as dat:
        sez_strnjenih = []
        for dogodek in dat:
            if n > 0 and prejsnja == dogodek:
                n += 1
                continue
            elif n == 2:
                sez_strnjenih.append("%s" % prejsnja[:-1])
            elif n > 2:
                sez_strnjenih.append("ponovljeno se %d-krat" % (n - 1))
            prejsnja = dogodek
            n = 1
            if dogodek:
                sez_strnjenih.append(dogodek.strip())
    return sez_strnjenih

2014.1.2 (napiši funkcijo)

Čopiči

1. podnaloga

V Ajdovščini tovarna Wlahna d. o. o. proizvaja krasne veganske bio čopiče, v celoti narejene iz lesa. Leseni ročaji so tako ali tako nekaj običajnega, v tej tovarni pa celó konico čopiča izdelajo iz lesa iste vrste, ki ga zmeljejo in predelajo v celulozna vlakna. V skladišču podjetja imajo lesene palčke enake debeline, a različnih dolžin, iz katerih želijo izdelati same enake čopiče. Za posamezen ročaj potrebujejo $r$ centimetrov lesa v enem kosu. Za konico čopiča pa potrebujejo toliko zmletega lesa, kot ga nastane iz $k$ centimetrov ene ali več palčk.

Naloga

Napiši funkcijo koliko_copicev(r, k, l), ki vrne število čopičev, ki jih podjetje s trenutno zalogo lesa lahko proizvede.

Vhodni podatki

r...dolžina palčke potrebne za en ročaj
k...dolžina palčke potrebna za eno konico
l...tabela dolžin palčk na zalogi v cm

Izhodni podatki

Zaokroženo naravno število, ki predstavlja največje število čopičev, ki jih podjetje lahko proizvede.

Primer

>>> koliko_copicev(20, 4, [423, 116, 235, 13, 119, 60])
40

Uradna rešitev

def koliko_copicev(k, r, l):
    """Izračuna največje število čopičev, ki jih lahko proizvedemo glede na dolžino
    enega ročaja r, dolžino palčke k, potrebne za 1 konico, ter tabelo dolžin palčk."""
    skup_dolzina = 0
    max_rocajev = 0
    for palica in l:
        skup_dolzina += palica
        max_rocajev += palica // r
    max_copicev = skup_dolzina // (k + r)
    if max_rocajev <= max_copicev:
        max_copicev = max_rocajev
    return max_copicev

2014.1.3 (napiši funkcijo)

Pacifistični generali

1. podnaloga

Ker imajo vse svetovne vojaške velesile jedrsko orožje, ga moramo nujno imeti tudi pri nas v Sloveniji. Vlada je na IJS naročila izdelavo jedrskih konic, od Rusov pa so kupili bojno plovilo vnl-11 Triglav, kjer so smrtonosne rakete zdaj shranjene. Dostopa do tako uničujočega orožja ne sme imeti kdorkoli, ampak ga ima samo peščica najpomembnejših generalov.

Ker bi se lahko med generali našel norec, ki bi za zabavo poslal raketo ali dve na katero od sosednjih republik, so se na vojaškem ministrstvu odločili za stroge varnostne ukrepe. Naročili so izdelavo $k$ različic ključev za aktivacijo jedrskih konic. Ključi so oštevilčeni s števili od $1$ do $k$. Vsaka različica ključa je bila izdelana v več izvodih.

Te ključe so nato razdelili med $n$ generalov tako, da je vsak prejel neko podmnožico (samih različnih) ključev. Označimo z $G_i$ podmnožico ključev, ki jih ima $i$-ti general. Skupina generalov lahko sproži atomsko bombo, če imajo vsi skupaj vsaj po eno kopijo vsakega od ključev.

Na ministrstvu so pred kratkim opazili fenomen, na katerega pri snovanju sistema sploh niso pomislili. Med generali je vedno več pacifistov, ki niso pod nobenimi pogoji pripravljeni uporabiti jedrskega orožja. Vlada se zdaj boji, da bi lahko manjša skupinica pacifistov ostalim generalom preprečila uporabo orožja. Rekli bomo, da je sistem $r$-odporen, če nobena skupina $r$ (ali manj) generalov ne more ostalim preprečiti aktivacije jedrskih konic.

Naloga

Napiši funkcijo odpornost(r, k, [G_1, ..., G_n]), ki bo za dani $r$ in dani sistem preverila, če je ta sistem $r$-odporen.

Vhodni podatki

Število $r$ predstavlja največje število pacifističnih generalov, ki ne morejo preprečiti sproženja jedrske rakete. Število $k$ predstavlja število ključev. V seznamu naborov $[G_1, ..., G_n]$ vsaka množica predstavlja ključe v lasti $i+1$-tega generala.

Omejitve vhodnih podatkov

Sistem ni večji od $10$ ključev in $10$ generalov.

Izhodni podatki

Funkcija vrne True ali False, ki se nanašata na to, ali je sistem $r$-odporen ali ne.

Primer

Recimo, da imamo $k = 3$ ključe in $n = 3$ generale. Naj bo

$G_1 = {1, 2}$
$G_2 = {2, 3}$
$G_3 = {1, 3}$

Prvi general ima torej ključ št. $1$ in ključ št. $2$. Drugi general ima ključ št. $2$ in ključ št. $3$. Tretji general ima ključ št. $1$ in ključ št. $3$. Vsak posamezni general ne more aktivirati jedrske konice, če pa se združita npr. prvi in drugi general, imata skupaj vse ključe.

$G_1 \cup G_2 = {1, 2, 3}$

Sistem iz zgleda je $1$-odporen, saj nobeden od generalov ne more sam 'blokirati' ostalih dveh.

Uradna rešitev

def odpornost(r, k, G):
    """Pove, ali je sistem ključev in generalov r-odporen ali ne."""
    st_pojavitev = [0] * k
    for general in G:
        for kljuc in general:
            st_pojavitev[kljuc - 1] += 1
    for i in range(k):
        if st_pojavitev[i] <= r:
            return False
        else:
            return True

2014.1.4 (napiši funkcijo)

Uniforme

1. podnaloga

Podjetje Wlahna d. o. o. se je odločilo svoje delavce obleči v praktične, trpežne uniforme iz debelega platna, skozi katerega jih ne bodo mogle bosti lesene trske, ki jih je v proizvodni hali podjetja vse polno. Uniforma sestoji iz treh kosov: hlač, jopiča in rokavic. Vsak kos uniforme je dobavljiv v velikostih od $1$ do $100$.

V podjetje je pravkar prispela nova pošiljka kosov uniform. Ko so jih razkladali s tovornjaka, so sproti popisali vsak kos uniforme (recimo: „hlače velikosti 73“). Zdaj jih zanima, koliko popolnih uniform lahko sestavijo. Popolna uniforma sestoji iz hlač, jopiča in rokavic v enaki velikosti.

Naloga

Napiši funkcijo stevilo_uniform(datoteka), ki prebere podatke o razpoložljivih kosih uniforme in vrne največje število popolnih uniform, ki se jih da sestaviti. Podatke naj bere iz datoteke, kodirane v utf-8.

Vhodni podatki

V prvi vrstici je zapisano število dostavljenih kosov $1 \leq n \leq 100$. Vsaka od naslednjih $n$ vrstic vsebuje dve števili, ločeni s presledkom, in opisuje posamezen kos uniforme. Prvo število ($1$, $2$, ali $3$) opisuje tip kosa (hlače, jopič, ali rokavice), drugo število (med $1$ in $100$) pa velikost.

  15
  3 98
  1 45
  1 74
  1 45
  2 98
  1 45
  2 45
  1 74
  2 74
  2 98
  2 74
  3 74
  3 74
  1 98
  2 74

Izhodni podatki

Največje število uniform, ki jih lahko sestavimo glede na zalogo. Za zgornje podatke:

>>> stevilo_uniform(zgornji_podatki)
3

Uradna rešitev

def stevilo_uniform(vhod):
    """Iz datoteke prebere podatke o zalogi ter poišče in vrne število
    popolnih uniform, ki jih lahko sestavimo."""
    zaloga = 100 * [0]   # različnih velikosti je 100
    for i in range(100):
        zaloga[i] = 3 * [0]
    max_uniform = 0
    with open(vhod, 'r', encoding='utf-8') as vhodna:
        for vrstica in vhodna:
            podatek = vrstica.strip().split(' ')
            if len(podatek) > 1:
                oblacilo = int(podatek[0])
                velikost = int(podatek[1])
                zaloga[velikost - 1][oblacilo - 1] += 1
    for i in range(100):
        velikost = zaloga[i]
        max_uniform += min(velikost)
    return max_uniform